The present invention is directed at relieving xe2x80x9ccongestionxe2x80x9d in communications networks. In particular, the present invention is directed at relieving congestion in a network which uses xe2x80x9cshortest pathxe2x80x9d routing techniques to manage data which is traversing, and congesting, the network.
The Internet is one example of such a network.
The Internet is a vast array of interconnected computers and computer systems. The ability to connect one personal computer to potentially a million other personal computers making up the Internet, requires a hierarchy of more sophisticated computers whose job is to xe2x80x9croutexe2x80x9d messages to and from these millions of computers in an efficient, fast and cost effective manner. These more sophisticated computers are aptly called xe2x80x9croutersxe2x80x9d. With the explosive growth of the Internet has come a need to use more sophisticated routers to insure that communications between computers on the Internet remains relatively trouble free. Problems due to xe2x80x9ccongestion,xe2x80x9d which occurs, broadly speaking, when there are not enough communication channels or available bandwidth on such channels to handle the volume of messages being sent, have begun to occur. When congestion occurs it usually results in an increase in connection and response time, where it takes longer to connect to the Internet and/or receive responses to a search or message.
Within a specific geographic area many routers are placed into a group called an xe2x80x9cautonomous systemxe2x80x9d (xe2x80x9cASxe2x80x9d). Usually, each AS is controlled by an entity known as an Internet Service Provider (xe2x80x9cISPxe2x80x9d). Thus, a message sent from Washington, D.C. to Philadelphia, Pa., for example, will typically travel over a number of ISPs each comprising their own array of routers. The routing of messages between ISPs connected to each other is typically performed using known xe2x80x9crouting protocolsxe2x80x9d. These protocols allow the respective routers within each ISP to xe2x80x9ctalkxe2x80x9d with each other. There are a number of protocols which may be used to allow such communications.
More specifically, it is important for a router to know where an incoming message is supposed to be sent. Each message has associated with it a destination Internet protocol (xe2x80x9cIPxe2x80x9d) address. Upon receiving the destination address, a router will use its embedded routing protocol to determine how best to forward the message to its final destination. Between the router which receives the message and the final destination of the message are any number of routers. Each successive router must select the next router in the chain of routers leading to the final destination. These next routers may be referred to as xe2x80x9cnext hopsxe2x80x9d. The particular protocol used by a router will determine the xe2x80x9cnext hopxe2x80x9d for the message. Once the message has been sent to a next hop router, this new router will repeat the process.
One class of routing protocols is known as a xe2x80x9clink statexe2x80x9d protocol. Routers using this type of protocol each share a combined database of information concerning all of the other routers within the same ISP. The information typically consists of the xe2x80x9cnetwork topologyxe2x80x9d and the xe2x80x9cweightxe2x80x9d of each communication xe2x80x9clinkxe2x80x9d. By network topology is meant the xe2x80x9croad mapxe2x80x9d of complex connections between each router in an ISP. Each connection may in turn comprise a number of smaller links. Each link has a given xe2x80x9cweightxe2x80x9d which governs the amount of xe2x80x9ctrafficxe2x80x9d or number of messages which may flow across each link depending on a variable, such as cost. A xe2x80x9cpathxe2x80x9d from one router to another may be created by xe2x80x9cstringingxe2x80x9d a number of xe2x80x9cweightedxe2x80x9d links together. Because each router has access to information about all of the links within an ISP, each router is able to determine a xe2x80x9cshortest pathxe2x80x9d from one router to another. Such a shortest path may include traversing a number of weighted links. Between each router there may exist a number of shortest paths or xe2x80x9cequal cost pathsxe2x80x9d (xe2x80x9cECPsxe2x80x9d).
Some specific link state protocols are xe2x80x9cOpen Shortest Path Firstxe2x80x9d and xe2x80x9cIntermediate System-Intermediate Systemxe2x80x9d protocols.
There may be hundreds, if not thousands of routers, in a pathway between the origin of a message and its eventual destination. Determining the shortest path through such an array of routers can be a daunting task; a task which is made even worse once this vast network of routers begins to become congested with traffic. Traditional approaches to managing congestion have faced two significant challenges. First, it has been thought that to effectively xe2x80x9cmanage congestionxe2x80x9d through a given router, the amount of traffic through each and every router in an AS must be known at any given period of time. More precisely, this would require each router to analyze each message coming into it by looking at each messages xe2x80x9coriginxe2x80x9d and xe2x80x9cdestinationxe2x80x9d address. Taking it one step further, because a given link consists of an xe2x80x9coriginxe2x80x9d router and a xe2x80x9cdestinationxe2x80x9d router (called an origin/destination or xe2x80x9cO/Dxe2x80x9d pair) it has been thought that what is needed is the ability to measure traffic flow (by origin and destination address) into and out of both the origin and destination routers. Even in a simple routing network, this task becomes insurmountable because of the thousands, if not millions, of messages and corresponding potential origin/destination addresses. If a router was asked to perform this task, its throughput would be greatly affected leading to a slower, less efficient pathway/network.
The second challenge relates to changing link weights. Again, a link""s weight affects the amount of traffic which will traverse the link. An increase or decrease in a link""s weight will increase or decrease traffic flow across that link. However, because each link is potentially a part of a million (for example) different paths, a simple change in one link may affect the traffic flow throughout each and every path which happens to include that link. Thus, attempts to decrease congestion through one link by changing its link weight would result in simply shifting the congestion to another link or path. Worse yet, the size and complex nature of the millions of paths connecting distant routers together makes the shifting of this congestion extremely unpredictable. Simply shifting traffic from one link to another may end up congesting a line of other links.
As mentioned initially, the Internet is only one type of network which utilizes routers and attempts to control congestion by looking at the xe2x80x9cshortest pathsxe2x80x9d between two O/D routing pairs. In general, congestion is a problem in many networks using multiple routers. When data traverses from one router to the next it is sometimes referred to as going xe2x80x9chop-by-hopxe2x80x9d or xe2x80x9cnext hop to next hop.xe2x80x9d In data communications, a single message may be broken up into xe2x80x9cpacketsxe2x80x9d of information which are routed xe2x80x9chop-by-hopxe2x80x9d.
To those skilled at the art, therefore, the problem becomes how to relieve congestion in hop-by-hop, routed packet networks. Accordingly, it is an object of the invention to provide for methods and devices which relieve congestion in hop-by-hop routed packet networks, such as the Internet.
It is another object of the invention to provide for such methods and devices which assume, contrary to present day wisdom, that the traffic flow through a pair of O/D routers in a given path cannot be determined and is, therefore, an unknown.
It is a further object of the present invention to provide for methods and devices which shift traffic flow from a congested link without congesting any additional links by either adjusting xe2x80x9csplitting factorsxe2x80x9d associated with the congested link and alternative paths or, when no such alternative paths exist, by creating new alternative paths and then adjusting the respective alternative paths.
It is yet a further object of the present invention to provide for programs for adjusting splitting factors and creating alternative paths which make use of xe2x80x9cvirtualxe2x80x9d networks.
It is still another object of the invention to provide for unique programs for deleting alternate paths which are no longer needed.
Other objectives, features and advantages of the present invention will become apparent to those skilled in the art from the following description taken in conjunction with the accompanying drawings.
In accordance with the present invention there are provided methods and devices which shift traffic flow from a congested link by adjusting the splitting factors associated with a congested link and alternative paths. Before traffic is shifted from a congested link, the present invention detects alternative shortest paths and then tests whether these alternative shortest paths are capable of receiving additional traffic. To minimize the disruption to a real world network, the tests are done by recreating the real world network as a virtual network. Only after an alternative shortest path has been tested and it has been determined that the path is capable of receiving additional traffic without disrupting the network or becoming congested itself is any traffic diverted from the congested link. The diversion or shifting of traffic from the congested link to an alternative, shortest path is carried out by changing the splitting factors associated with the congested link and the alternative path.
Sometimes no such alternative paths may be detected, i.e., none exist. The present invention then envisions methods and devices which create new alternative, shortest paths. These paths are created, again, by using a virtual network representation. In order to qualify as a new, shortest path, a path must meet a strict set of criteria to insure that the existing network is not disrupted. The new shortest paths are created by changing the link weights of the congested link and qualified paths.
In the event that traffic through a network decreases the present invention also envisions methods and devices for eliminating those paths or links which become inefficient. Inefficient paths are xe2x80x9cremovedxe2x80x9d from the network by decreasing the splitting factor associated with a given inefficient path. Decreasing the splitting factor results in a likewise decrease in traffic over the link. The splitting factor may be decreased until there is no traffic moving over the inefficient link, thus, effectively removing it from the network.
The present invention and its advantages can be best understood with reference to the drawings, detailed description of the preferred embodiments and claims that follow.